package org.algorithm.Sort;

import java.util.Enumeration;

public class HeapSort1 {
    public static void main(String[] args) {
        int [] nums ={2,3,6,4,9,5,1};
        heapSort(nums,nums.length);
        for(int num:nums){
            System.out.println(num);
        }
    }

    public static void heapSort(int [] nums,int n){
        //生成顶堆
        for (int i = (n/2)-1; i >=0 ; i--) {
            heapify(nums,i,n);
        }

        //将堆顶元素与最后一个元素交换，并重新堆化
        for (int i = 0; i < n; i++) {
            swap(nums,0,n-i-1);
            heapify(nums,0,n-i);
        }
    }

    public static void heapify(int [] nums,int rootIndex,int n){
        int leftIndex = 2*rootIndex+1;
        int rightIndex = 2*rootIndex+2;
        int maxIndex = rootIndex;
        if (leftIndex<n && nums[maxIndex]<nums[leftIndex]){
            maxIndex= leftIndex;
        }

        if (rightIndex<n && nums[maxIndex]<nums[rightIndex]){
            maxIndex= rightIndex;
        }

        if (maxIndex!=rootIndex){
            swap(nums,maxIndex,rootIndex);
            heapify(nums,maxIndex,n);
        }
    }

    private static void swap(int []nums,int index1,int index2){
        int temp = nums[index1];
        nums[index1]=nums[index2];
        nums[index2]=temp;
    }



}
